package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;

import org.junit.Test;
import util.TreeNode;

/**
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 * 任意两个节点之间的最大长度：两个节点之间是一个长度
 *
 * 思路分析：
 *      一条路径的长度为该路径经过的节点数减一，所以求直径等效于求路径经过节点数的最大值减一。
 *      任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
 *
 *      先求总的节点数 result = l + r + 1，最后返回路径长度 result - 1
 *      通过递归计算各个节点为根节点时的总结点数，并更新记录最大值
 *
 */
public class _022_二叉树的直径长度 {

    private int result = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return result-1;
    }

    public int dfs(TreeNode root) {
        if(root==null) return 0;

        int l = dfs(root.left);
        int r = dfs(root.right);

        // System.out.println(root.val + " : " + (l+r+1));
        result = Math.max(result, r+l+1);

        return Math.max(l, r) + 1;
    }


    @Test
    public void main() {
        Integer[] integers = {1, 2, 3, 4, 5};
        TreeNode root = TreeNode.getTreeFromArray(integers);
        System.out.println(diameterOfBinaryTree(root));
    }
}
